package dynProg.solvers;

public class BottomUpSolver implements Solver {

	@Override
	public boolean solve(int[] numbers, int sum) {
        int n = numbers.length - 1;
        boolean[][] solution = new boolean[n + 1][sum + 1];
        for(int index = 0; index < sum + 1; index++){
            solution[0][index] = index == 0 || numbers[0] == index ;
        }

        int row = 1;
        while(n >= row){
            for(int col = 0; col < sum + 1; col++){
                solution[row][col] = col == numbers[row] || solution[row - 1][col];
                if(col - numbers[row] >= 0){
                    solution[row][col] |= solution[row - 1][col - numbers[row]];
                }
            }
            row++;
        }

        return solution[n][sum];
	}

}
